class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		if (grid.size() == 0 || grid[0].size() == 0) {
			return 0;
		}

		int n = grid.size();
		int m = grid[0].size();
		vector<vector<int> > dp(n, vector<int>(m));

		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (i - 1 >= 0 && j - 1 >= 0) {
					dp[i][j] = min(dp[i - 1][j] + grid[i][j],
								   dp[i][j - 1] + grid[i][j]);
				} else if (i - 1 >= 0) {
					dp[i][j] = dp[i - 1][j] + grid[i][j];
				} else if (j - 1 >= 0) {
					dp[i][j] = dp[i][j - 1] + grid[i][j];
				} else {
					dp[i][j] = grid[i][j];
				}
			}
		}
		return dp[n - 1][m - 1];
	}
};